package com.kangkang.leetcode20;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Test2861 {
    public static void main(String[] args) {

        int[][] arr = {{1,1,1},{1,1,10}};
        List<List<Integer>> composition= new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(1);
        list1.add(1);
        composition.add(list1);
        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(1);
        list2.add(1);
        list2.add(10);
        composition.add(list2);
        ArrayList<Integer> stock = new ArrayList<>();
        stock.add(0);
        stock.add(0);
        stock.add(0);
        ArrayList<Integer> cost = new ArrayList<>();
        cost.add(1);
        cost.add(2);
        cost.add(3);
        System.out.println(new Solution2861().maxNumberOfAlloys(3, 2, 15, composition, stock, cost));
    }
}
class Solution2861 {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int left = 0;
        int right = 200000000;
        int mid =200000000/2;
        while (left<=right){
            long minimumAmount = Long.MAX_VALUE;//制造mid量的合金的最少花费
            for (int i = 0; i < k; i++) {
                //用第i种机器制造mid份合金所需金额
                long Amount = 0;
                for (int j = 0; j < n; j++) {
                    Amount += Math.max((long)composition.get(i).get(j)*mid-stock.get(j),0)*cost.get(j);//所需第j种合金数
                }
                minimumAmount = Math.min(minimumAmount,Amount);
            }
            if(minimumAmount>budget){
                //造不了

                right=mid-1;
            }else{
                //能造

                left=mid+1;
            }
            mid = (left + right)/2;
        }
        return mid;
    }
}